package com.dyz.swordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/5/30 18:55
 * @description:
 */
public class Match19 {
    public static void main(String[] args) {
        String str = "aaa";
        String pattern = "ab*ac*a";
        boolean match = new Match19().match(str, pattern);
        System.out.println(match);
    }
    //使用动态规划求解
    public boolean match (String str, String pattern) {
        // write code here
        int s = str.length();
        int p = pattern.length();
        boolean[][] dp = new boolean[s + 1][p + 1];//00 用于存放两个空字符串的结果 dp[i][j] 表示模式串前j个是否与字符串前i个匹配
        for (int i = 0; i <= s; i++) {//实际上模式串和字符串的起点为1(所以后面的下标都是i-1 j-1)
            for (int j = 0; j <= p; j++) {
                if (j == 0) {
                    dp[i][j] = (i == 0);//只有字符串和模式串都为空的时候才匹配，当模式串为空，字符串不为空则返回false
                } else {
                    if (pattern.charAt(j - 1) != '*') {//如果第j-1个字符不是*
                        if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')) {
                            //正常匹配
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    } else {//如果第j个是* 那么分两种情况，有一种成立即可
                        //case 1 可以直接忽略*前模式的那个元素（*代表出现0次 比如a* 这两个元素做空字符串）
                        //那么dp[i][j]==true 只需满足 dp[i][j-2]==true即可
                        if (j >= 2) {
                            dp[i][j] = dp[i][j - 2];
                        }
                        //case 2 如果dp[i][j-2]不等于true那么要满足第j-1个字符(这个字符也可以为‘.’)与第i个字符匹配即可
                        //下标多减1是因为dp是从1开始记录的
                        if (i > 0 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')) {
                            dp[i][j] |= dp[i - 1][j];//使用或等于 两种情况有一种符合就行
                        }
                    }
                }
            }
        }
        return dp[str.length()][pattern.length()];
    }

    //搜索的方法
    public boolean match1 (String str, String pattern) {

        return solve(str, pattern, 0,0);

    }

    private boolean solve(String s, String p, int index1, int index2){
        //递归终止条件
        if(index1==s.length() && index2==p.length()){
            return true;
        }

        if(index1==s.length() || index2==p.length()){
            if(index1==s.length()){
                return  change(p,index2);
            }else {
                return false;
            }
        }

        //判断当前下标的下一个下标是否有“*”
        if(index2+1<p.length() && p.charAt(index2+1)== '*'){ //*表示前面的字符可以出现任意次数，包括0次
            //当当前下标的字符相等时
            if(judge(s.charAt(index1), p.charAt(index2))){
                //如 abba ab*bba  0次 或者 abbbba    ab*a >=1次
                return  solve(s, p, index1, index2+2) || solve(s, p, index1+1, index2);


            }else {
                //当前下标的字符不相等的时候，*前面的字符让他出现0次, 如 aaa  ab*ac*a
                return solve(s, p, index1, index2+2);
            }

        }
        if(judge(s.charAt(index1), p.charAt(index2))){//当前两个下标所指的字符匹配
            return solve(s,p , index1+1, index2+1);
        }
        return false;
    }

    private boolean change(String p, int index2) {
        while (index2<p.length()){
            if(index2+1<p.length()&&p.charAt(index2+1)=='*'){
                index2+=2;
            }else {
                return false;
            }
        }
        return true;
    }

    private boolean judge(char s1, char s2) {
        if(s1 == s2 || s2 == '.'){
            return  true;
        }
        return  false;
    }

}
